OK, so welcome back.

We're talking about adversarial search,

or you can think of that as game playing.

The idea here is that we're extending the methods we

learned last week on search to the setting where we're

in a two-agent system, where there is an adversary, somebody

trying to win and therefore do evil to our moves.

We looked into essentially doing the math of this.

And doing the math is relatively simple.

You take all the infrastructure we have for search

and just basically slices down the middle,

divide it into a white and black part.

And that translates into an algorithm for minimax search,

which is essentially the idea that you get a search

tree that is layered.

Max's turns followed by min's turns

by Max's turns by min's turns.

Max can control only those parts of the search,

only those levels where it's his move.

And then we really looked at the minimax algorithm.

And that is really all about exploring this layered tree

down there until you get to the terminal states.

Then you look up the utilities.

Did I win or did I lose?

And then you propagate the utilities up the tree again,

maximizing, minimizing, maximizing, minimizing.

That's the propagation.

And that gives you guidance.

These numbers we're propagating up.

Gives you guidance on which move to take.

Works very nicely in theory, in practice,

for all of the interesting games, which literally

means anything but tic-tac-toe.

This is infeasible.

The search spaces are just too big.

And what we're doing essentially is

we're trying to mitigate this problem in some way.

One of the ways was by introducing heuristics.

We call them evaluation functions in gameplay

and the idea is that you can actually,

by looking at your material, for instance, in chess,

how many pawns and kings and queens and so on do you have,

then you can actually decide how good it looks for you

by comparing your material to the material of your opponent.

And so something is not doing what I want it to do.

The typical thing here is to take an approach that

is often called the attribute or feature-based approach,

where you basically give yourself

a set of functions called features or attributes

on the states that give you some numeric information